//01背包
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class test {
    public static int N = 1005;

    //----------二维解法----------
    public static void main0() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        // v->体积  w->价值
        int[] v = new int[N];
        int[] w = new int[N];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        // 1. 创建dp表
        // 代表选择第 i 个物品时,背包最大有 j 个空间情况下,能存放的最大价值
        int[][] dp = new int[N][N];
        // 2. 初始化(第一问)

        // 3. 填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                // 不装入该物品(仍保持上次的最高值)
                dp[i][j] = dp[i - 1][j];
                // 装入该物品
                if (j >= v[i]) {
                    // 比如背包的空间有10,如果此时的物品体积为3
                    // 那么说明剩余体积小于3时,无法存放该物品 -> (j >= v[i])
                    // 当我们想把体积为3的物品放入5的位置时,
                    // 按理来说我们要在[1,4]的范围内找到一个最大值,再加上w[i]
                    // 但这个最大值不是随便找的,这个最大值的前提是[要给当前物品留有充足空间]
                    // 而这个充足空间就代表 [j - v[i]]
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        // 4. 返回值
        System.out.println(dp[n][V]);
        // 2. 初始化(第二问)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = 0;
            }
        }
        // 以-1代表 选择到第 i 个物品时,不存在正好装满 j 个空间的情况.
        for (int i = 1; i <= V; i++) {
            dp[0][i] = -1;
        }
        // 3. 填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                // 不装入该物品(仍保持上次最高值)
                dp[i][j] = dp[i - 1][j];
                // 当包内剩余空间足够时,我们必须判断放入当前物品后
                // 是否能够使背包达到装满的情况,比如:
                // 如果背包空间为10,当前物品体积为3,按照(第一问)的逻辑
                // 我们能对[0,7]的位置进行检查判断,但是直接装入,有可能发生
                // (对4位置装入,代表[4~6]存在物品,而[0~3]可能仍然为空
                // 所以我们必须确保,在4位置装入之前,3位置装满的情况存在)
                // 也就是 dp[i - 1][j - v[i]] >= 0;
                if (j >= v[i] && dp[i - 1][j - v[i]] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V] > 0 ? dp[n][V] : 0);
    }

    //----------一维解法----------
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N];
        int[] w = new int[N];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        // 1. 创建dp表
        // 代表背包空间为 j 时,能够存储的最大价值
        int[] dp = new int[N];
        // 2. 初始化(第一问)

        // 3. 填表
        // 在二维数组解题时,我们需要用到[上一列同一位置]和[上一列左侧位置]
        // 而使用一维数组解题时,当前数组存储的就是[上一列的数据]
        // 从左往右的顺序会导致,[检查时使用左侧数据,可能已经被顶替],故改变遍历顺序
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= 1; j--) {
                //不装入该物品(仍保持上次最高值)
                //从右往左重新遍历时,[j]左侧元素都代表上次的值
                //所以未修改时,dp[j]就代表上次的最高值 -> dp[j] = dp[j]
                //装入该物品,与二维解法思路相同
                if (j >= v[i]) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
        }
        // 4. 返回值
        System.out.println(dp[V]);

        // 2. 初始化(第二问)
        for (int j = 0; j <= V; j++) {
            dp[j] = -1;
        }
        dp[0] = 0;
        // 3. 填表
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= 1; j--) {
                //不装入该物品(仍保持上次最高值) -> 同上
                //装入该物品,与二维解法思路相同
                if (j >= v[i] && dp[j - v[i]] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
        }
        // 4. 返回值
        System.out.println(dp[V] >= 0 ? dp[V] : 0);
    }
}
